package 力扣._51N皇后;

import java.util.*;

class Solution {
    Set<Integer> columns = new HashSet<>();
    Set<Integer> diagonals1 = new HashSet<>();
    Set<Integer> diagonals2 = new HashSet<>();

    public List<String> generateBoard(int[] queens, int n) {
        List<String> board = new ArrayList<String>();
        for (int i = 0; i < n; i++) {
            char[] row = new char[n];
            Arrays.fill(row, '.');
            row[queens[i]] = 'Q';
            board.add(new String(row));
        }
        return board;
    }

    private void trackBack(List<List<String>> solutions, int[] queens, int n, int row) {
        if (row == n) {
            List<String> board = generateBoard(queens, n);
            solutions.add(board);
            return;
        }
        for (int j = 0; j < n; j++) {
            if (columns.contains(j))
                continue;
            if (diagonals1.contains(row - j))
                continue;
            if (diagonals2.contains(row + j))
                continue;

            columns.add(j);
            diagonals1.add(row - j);
            diagonals2.add(row + j);
            queens[row] = j;

            trackBack(solutions, queens, n, row + 1);
            // 恢复现场
            queens[row] = -1;
            columns.remove(j);
            diagonals1.remove(row - j);
            diagonals2.remove(row + j);
        }

    }


    public List<List<String>> solveNQueens(int n) {
        List<List<String>> solutions = new ArrayList<List<String>>();
        int[] queens = new int[n];
        Arrays.fill(queens, -1);
        trackBack(solutions, queens, n, 0);
        return solutions;

    }

    public static void main(String[] args) {
        List<List<String>> lists = new Solution().solveNQueens(8);
        for (List<String> list : lists) {
            System.out.println(list);
        }
    }
}